#define _CRT_SECURE_NO_WARNINGS

class Solution {
public:
    void _treeToDoublyList(Node* root, Node*& previous)
    {
        if (root == nullptr)
            return;
        _treeToDoublyList(root->left, previous);

        root->left = previous;
        if (previous)
            previous->right = root;

        previous = root;

        _treeToDoublyList(root->right, previous);
    }

    Node* treeToDoublyList(Node* root) {
        if (root == nullptr)
            return nullptr;
        Node* previous = nullptr;

        Node* left = root;
        while (left->left)
        {
            left = left->left;
        }
        Node* right = root;
        while (right->right)
        {
            right = right->right;
        }
        _treeToDoublyList(root, previous);

        left->left = right;
        right->right = left;

        return left;
    }
};